/*
    * Copyright (C) 2012 The Guava Authors
    *
    * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
    * in compliance with the License. You may obtain a copy of the License at
    *
    * http://www.apache.org/licenses/LICENSE-2.0
    *
    * Unless required by applicable law or agreed to in writing, software distributed under the License
   * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
   * or implied. See the License for the specific language governing permissions and limitations under
   * the License.
   */
  
  package com.google.common.collect;
  
  import com.google.caliper.BeforeExperiment;
  import com.google.caliper.Benchmark;
  import com.google.caliper.Param;
  import com.google.common.base.Optional;
  import com.google.common.primitives.Ints;
  
  import java.util.List;
  import java.util.Random;
  
  /**
   * Benchmarks for the {@code TreeTraverser} and optimized {@code BinaryTreeTraverser} operations on
   * binary trees.
   *
   * @author Louis Wasserman
   */
  public class BinaryTreeTraverserBenchmark {
    private static class BinaryNode {
      final int x;
      final Optional<BinaryNode> left;
      final Optional<BinaryNode> right;
  
      BinaryNode(int x, Optional<BinaryNode> left, Optional<BinaryNode> right) {
        this.x = x;
        this.left = left;
        this.right = right;
      }
    }
  
    enum Topology {
      BALANCED {
        @Override
        Optional<BinaryNode> createTree(int size, Random rng) {
          if (size == 0) {
            return Optional.absent();
          } else {
            int leftChildSize = (size - 1) / 2;
            int rightChildSize = size - 1 - leftChildSize;
            return Optional.of(new BinaryNode(
                rng.nextInt(), createTree(leftChildSize, rng), createTree(rightChildSize, rng)));
          }
        }
      },
      ALL_LEFT {
        @Override
        Optional<BinaryNode> createTree(int size, Random rng) {
          Optional<BinaryNode> root = Optional.absent();
          for (int i = 0; i < size; i++) {
            root = Optional.of(new BinaryNode(rng.nextInt(), root, Optional.<BinaryNode>absent()));
          }
          return root;
        }
      },
      ALL_RIGHT {
        @Override
        Optional<BinaryNode> createTree(int size, Random rng) {
          Optional<BinaryNode> root = Optional.absent();
          for (int i = 0; i < size; i++) {
            root = Optional.of(new BinaryNode(rng.nextInt(), Optional.<BinaryNode>absent(), root));
          }
          return root;
        }
      },
      RANDOM {
        /**
         * Generates a tree with topology selected uniformly at random from the topologies of binary
         * trees of the specified size.
         */
        @Override
        Optional<BinaryNode> createTree(int size, Random rng) {
          int[] keys = new int[size];
          for (int i = 0; i < size; i++) {
            keys[i] = rng.nextInt();
          }
          return createTreap(Ints.asList(keys));
        }
        
        // See http://en.wikipedia.org/wiki/Treap for details on the algorithm.
        private Optional<BinaryNode> createTreap(List<Integer> keys) {
          if (keys.isEmpty()) {
            return Optional.absent();
          }
          int minIndex = 0;
          for (int i = 1; i < keys.size(); i++) {
           if (keys.get(i) < keys.get(minIndex)) {
             minIndex = i;
           }
         }
         Optional<BinaryNode> leftChild = createTreap(keys.subList(0, minIndex));
         Optional<BinaryNode> rightChild = createTreap(keys.subList(minIndex + 1, keys.size()));
         return Optional.of(new BinaryNode(keys.get(minIndex), leftChild, rightChild));
       }
     };
 
     abstract Optional<BinaryNode> createTree(int size, Random rng);
   }
 
   private static final BinaryTreeTraverser<BinaryNode> BINARY_VIEWER =
       new BinaryTreeTraverser<BinaryNode>() {
 
     @Override
     public Optional<BinaryNode> leftChild(BinaryNode node) {
       return node.left;
     }
 
     @Override
     public Optional<BinaryNode> rightChild(BinaryNode node) {
       return node.right;
     }
   };
   
   private static final TreeTraverser<BinaryNode> VIEWER = new TreeTraverser<BinaryNode>() {
     @Override
     public Iterable<BinaryNode> children(BinaryNode root) {
       return BINARY_VIEWER.children(root);
     }
   };
 
   enum Traversal {
     PRE_ORDER {
       @Override
       <T> Iterable<T> view(T root, TreeTraverser<T> viewer) {
         return viewer.preOrderTraversal(root);
       }
     },
     POST_ORDER {
       @Override
       <T> Iterable<T> view(T root, TreeTraverser<T> viewer) {
         return viewer.postOrderTraversal(root);
       }
     },
     BREADTH_FIRST {
       @Override
       <T> Iterable<T> view(T root, TreeTraverser<T> viewer) {
         return viewer.breadthFirstTraversal(root);
       }
     };
 
     abstract <T> Iterable<T> view(T root, TreeTraverser<T> viewer);
   }
 
   private Iterable<BinaryNode> view;
   
   @Param
   Topology topology;
 
   @Param({"1", "100", "10000", "1000000"})
   int size;
 
   @Param
   Traversal traversal;
   
   @Param
   boolean useBinaryTraverser;
   
   @Param({"1234"})
   SpecialRandom rng;
 
   @BeforeExperiment
   void setUp() {
     this.view = traversal.view(
         topology.createTree(size, rng).get(), 
         useBinaryTraverser ? BINARY_VIEWER : VIEWER);
   }
 
   @Benchmark int traversal(int reps) {
     int tmp = 0;
 
     for (int i = 0; i < reps; i++) {
       for (BinaryNode node : view) {
         tmp += node.x;
       }
     }
     return tmp;
   }
 }